package sortingBasic.detectPerformance;

import sortingBasic.generateCase.SortHelper;

/**
 * 选择排序
 * mxf
 * 2018年5月18日15:07:06
 * 像是摸牌，摸出一张挨个与后面的元素进行比较，on²级别
 */
public class SelectionSort {

    private SelectionSort(){}

    public static void sort(Comparable[] arr) {
        int length = arr.length;
        for(int i = 0; i < length; i++) {
            int minIndex = i;// 最小索引
            // 与[i+1, length)逐一进行比较
            for(int j = i + 1; j < length; j++) {
                if(arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    // 两数组元素交换位置
    public static void swap(Object[] arr , int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        Integer[] arr = SortTestHelper.generateRandomArray(100, 1, 1000);
        SortTestHelper.testSort("sortingBasic.detectPerformance.SelectionSort", arr);
    }
}
